#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

void gen_knuth(int m, int n)
{
    int i;

    for (i = 0; i < n; i++) {
        if ((rand()%(n-i)) < m) {
            printf("%d ", i);
            m --;
        }
    }
    printf("\n");
}

void gen_hash(int m, int n)
{
    int i, t, a[n];
    
    memset(a, 0, n*(sizeof(int)));
    for (i = 0; i < m; i++) {
        t = rand()%n;
        while (a[t] != 0)
            t = (t+1)%n;
        a[t] = 1;
        printf("%d ", t);
    }
    printf("\n");
}

void gen_swap(int m, int n)
{
    int a[n], i, t;

    for (i = 0; i < n; i++) {
        a[i] = i;
    }

    for (i = 0; i < m; i++) {
        t = rand()%n;
        a[i] = a[i] ^ a[t];
        a[t] = a[i] ^ a[t];
        a[i] = a[i] ^ a[t];
        printf("%d ", a[i]);
    }
    printf("\n");
}

int randint(int i, int u)
{
    int num = (rand() << 15) & rand();

    return num%(u-i+1) + i;
}

int main(int argc, char *argv[])
{
    int m = 4, n = 1000000, i;

    srand(time(NULL));
    gen_knuth(m, n);
    gen_hash(m, n);
    gen_swap(m, n);

    for (i = 0; i < 10; i++) {
        printf("%d ", randint(10, 30));
    }
    printf("\n");

    return 0;
}
